package chart.mst;

import chart.UnionFindSet;
import chart.图的存储.AbstractGraph;
import chart.图的存储.AdjacencyMatrix;
import chart.图的存储.AdjacencyTable;
import chart.图的存储.Edge;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 库鲁斯卡尔算法
 * <p>针对边</p>
 * <p>贪心</p>
 * <p>适用于稀疏图</p>
 * <p>算法要点：</p>
 * <p>对边进行排序</p>
 * <p>使用并查集判断顶点是否属于同一棵树</p>
 *
 * <p>时间复杂度：O(ElogE)</p>
 *
 * @author yezh
 * @date 2023/7/10 17:17
 */
public class Kruskal {

    public static void main(String[] args) {
        Edge e1 = new Edge(0, 1, 2);
        Edge e2 = new Edge(0, 2, 1);
        Edge e3 = new Edge(1, 2, 4);
        Edge e4 = new Edge(1, 3, 2);
        Edge e5 = new Edge(2, 3, 1);
        List<Edge> edges = Arrays.asList(e1, e2, e3, e4, e5);

        AbstractGraph graph = new AdjacencyMatrix(4, false);
        graph.createGraph(edges);
        System.out.println(doKruskal(graph));
        System.out.println(doKruskalWithHeap(graph));

        graph = new AdjacencyTable(4, false);
        graph.createGraph(edges);
        System.out.println(doKruskalWithHeap(graph));
    }

    public static int doKruskal(AbstractGraph graph) {
        int ans = 0;
        List<Edge> edges = graph.allEdge();
        edges.sort(Comparator.comparingInt(Edge::getWeigh));
        UnionFindSet unionAndFind = new UnionFindSet(graph.getV());
        for (Edge edge : edges) {
            int r1 = unionAndFind.findOptimize(edge.getArcTail());
            int r2 = unionAndFind.findOptimize(edge.getArcHead());
            if (r1 != r2) {
                unionAndFind.unionOptimize(edge.getArcTail(), edge.getArcHead());
                ans += edge.getWeigh();
                System.out.println("arcTail: " + edge.getArcTail() + ", arcHead: " + edge.getArcHead() + ", weigh: " + edge.getWeigh());
            }
        }
        return ans;
    }

    public static int doKruskalWithHeap(AbstractGraph graph) {
        Edge[] edges = graph.getAllEdge();
        int e = edges.length;
        for (int i = e / 2 - 1; i >= 0; i--) heapify(i, edges, e);

        int res = 0;
        UnionFindSet unionFindSet = new UnionFindSet(graph.getV());
        for (int i = e - 1; i >= 0; i--) {
            Edge edge = edges[0];
            int r1 = unionFindSet.findOptimize(edge.getArcTail());
            int r2 = unionFindSet.findOptimize(edge.getArcHead());
            if (r1 != r2) {
                unionFindSet.unionOptimize(edge.getArcTail(), edge.getArcHead());
                res += edge.getWeigh();
                System.out.println("arcTail: " + edge.getArcTail() + ", arcHead: " + edge.getArcHead() + ", weigh: " + edge.getWeigh());
            }
            edges[0] = edges[i];
            heapify(0, edges, i);
        }
        return res;
    }

    private static void heapify(int k, Edge[] edges, int len) {
        Edge edge = edges[k];
        for (int i = 2 * k + 1; i < len; i = 2 * k + 1) {
            if (i + 1 < len && edges[i + 1].getWeigh() < edges[i].getWeigh()) i++;
            if (edges[i].getWeigh() < edge.getWeigh()) {
                edges[k] = edges[i];
                k = i;
            } else break;
        }
        edges[k] = edge;
    }

}
